package n3292;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int p[]=new int[1000010];
	static int is[]=new int[1000010];
	static int sp[]=new int[1000010];//记录H-semi-prim
	static int count;
	static void init() {
		Arrays.fill(is, 0);
		for(int i=5;i<1000002;i+=4)
		{
			for(int j=5;j<1000002;j+=4)
			{
				int k=i*j;
				if(k>1000001)break;
				if(is[i]==0&&is[j]==0)//i,j都为H-prim
				{
					is[k]=1;//H-semi-prim
				}else{
					is[k]=-1;//H-composite
				}
			}
		}
		for(int i=5;i<1000002;i++)
		{
			if(is[i]==1)
			{
				count++;
			}
			sp[i]=count;
		}
	}
	
	/**
	 * 普通的求h-prim的筛选方法
	 *
	 */
	static void init2()
	{
		Arrays.fill(is, 0);
		for(int i=5;i<1000002;i+=4)
		{
			if(is[i]==0)
			{
				p[count++]=i;
				for(int j=0;j<count&&i*p[j]<1000002;j++)
				{
					is[i*p[j]]=1;
					if(i%p[j]==0)break;
				}
				if(count<100)System.out.println(i);
			}
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {

		init2();
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String line=null;
		while((line=bf.readLine())!=null)
		{
			if(line.equals("0"))break;
			int n=Integer.parseInt(line);
			System.out.println(n+" "+sp[n]);
		}
	}

}
